{
 "metadata": {
  "name": "",
  "signature": "sha256:6cab3e49f03815fcb1a4d24d2cf3da78366bb75bc50a58e5a6538a4b0f640990"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random\n",
      "import operator\n",
      "import numpy as np \n",
      "from copy import deepcopy\n",
      "\n",
      "class point:\n",
      "    def __init__(self,listLine):\n",
      "        self.feature = listLine\n",
      "        self.label = None           \n",
      "class label:\n",
      "    def __init__(self,listLine):\n",
      "        self.feature = listLine\n",
      "        self.cluster = []"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# \u8f09\u5165data\n",
      "filenamme = '/Users/wy/Desktop/kmean_data.txt'\n",
      "points=[]\n",
      "\n",
      "with open (filenamme,'r') as f:\n",
      "    lines = f.readlines()\n",
      "    \n",
      "for index, line in enumerate(lines):\n",
      "    line=line.strip()   \n",
      "    listLine = map(float,line.split(' '))\n",
      "    # \u521d\u59cb\u5316 points\n",
      "    tmp = point(listLine)\n",
      "    points.append(tmp)\n",
      "    \n",
      "# \u591a\u5c11\u7dad\u5ea6    \n",
      "dimension = len(listLine)\n",
      "\n",
      "# \u521d\u59cb\u5316 label\n",
      "def initialization_label(k,points):\n",
      "    labels=[]\n",
      "    # random\u4ee5\u5229\u65bc\u96a8\u6a5f\u521d\u59cblabel\n",
      "    new_points = deepcopy(points)\n",
      "    np.random.shuffle(new_points)  \n",
      "    for index, line in enumerate(new_points[:k]):\n",
      "        index = label(line.feature)\n",
      "#         print(line.feature)\n",
      "        labels.append(index) \n",
      "    return labels"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# show points labels and feature\n",
      "def show_points(points):\n",
      "    for index, item in enumerate(points):\n",
      "        t=\"\"\n",
      "        for findex, fitem in enumerate(item.feature):\n",
      "            t += str(findex)+':'+str(fitem)+'\\t'\n",
      "        print(str(index)+':'+\"\u5206\u985e\"+str(item.label)+\"\\tfeature-\"+str(t))\n",
      "        \n",
      "# show labels feature        \n",
      "def show_labels(labels):\n",
      "    for index, item in enumerate(labels):\n",
      "        t=\"\"\n",
      "        for findex, fitem in enumerate(item.feature):\n",
      "            t += str(findex)+':'+str(fitem)+'\\t'\n",
      "        print(\"label\"+str(index)+\"\\tfeature-\"+str(t))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def kmeans(k,labels,points,num_basic_kmeans):\n",
      "    # sse = sum of square error\n",
      "    sse=0\n",
      "    \n",
      "    # \u6e05\u7a7a label \u7684 cluster \u4fbf\u65bc\u4e4b\u5f8c\u91cd\u65b0\u5206\u914d\u9ede\u7684label\n",
      "    for a in range(len(labels)):\n",
      "        labels[a].cluster=[]\n",
      "        \n",
      "    # step1: cluster assignment\n",
      "    for a in range(len(points)):\n",
      "        # \u8a08\u7b97\u6700\u5c0f\u7684\u8ddd\u96e2\u4e4blist\n",
      "        tp=[]\n",
      "        for b in range(len(labels)):\n",
      "            point_features_error=0\n",
      "            for c in range(dimension):\n",
      "                point_features_error += (labels[b].feature[c]-points[a].feature[c])**2\n",
      "            tp.append(point_features_error)            \n",
      "        points[a].label = tp.index(min(tp))+num_basic_kmeans\n",
      "        sse+=tp[tp.index(min(tp))]\n",
      "        # labes \u52a0\u5165 \u88ab\u5206\u914d\u7684\u9ede\n",
      "        labels[ tp.index(min(tp)) ].cluster.append(points[a])     \n",
      "        \n",
      "    # step2: move centroid\n",
      "    for a in range(len(labels)):\n",
      "        if len(labels[a].cluster) !=0:\n",
      "            for c in range(dimension):\n",
      "                temp = 0\n",
      "                for b in range(len( labels[a].cluster )):\n",
      "                    temp+=labels[a].cluster[b].feature[c]\n",
      "                labels[a].feature[c]=float(temp)/float(len(labels[a].cluster))  \n",
      "                \n",
      "    # return labels \u7528\u65bc basic_kmeans\n",
      "    return (sse , labels)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# basic_kmeans\n",
      "def basic_kmeans(k,points,num_basic_kmeans,times):\n",
      "    labels = optimization(k,points,times)\n",
      "    psse, plabelList = kmeans(k,labels,points,num_basic_kmeans)\n",
      "    sse, labelList = kmeans(k,labels,points,num_basic_kmeans)\n",
      "    count=1\n",
      "    while psse != sse:\n",
      "        psse = sse\n",
      "        sse, labelList = kmeans(k,labels,points,num_basic_kmeans)\n",
      "        count += 1\n",
      "    return (sse , labelList)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# costfunction \u7b97\u51fa sse = sum of square error\n",
      "def costfunction(labels,points):\n",
      "    # sse = sum of square error\n",
      "    sse=0\n",
      "    for a in range(len(points)):\n",
      "        # \u8a08\u7b97\u6700\u5c0f\u7684\u8ddd\u96e2\u4e4blist\n",
      "        tp=[]\n",
      "        for b in range(len(labels)):\n",
      "            point_features_error=0\n",
      "            for c in range(dimension):\n",
      "                point_features_error += (labels[b].feature[c]-points[a].feature[c])**2\n",
      "            tp.append(point_features_error)            \n",
      "        sse+=tp[tp.index(min(tp))]\n",
      "    return sse"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# bisecting_Kmeans\n",
      "def bisecting_Kmeans(points,nbk,times):\n",
      "    # \u57f7\u884c\u7b2c\u4e00\u6b21 bisecting_Kmeans t=0\n",
      "    sse,labels = basic_kmeans(2,points,0,times)\n",
      "    # bisecting_Kmeans \u4e2d points\u7686\u6703\u5206\u6210\u5169\u985e labels[0],labels[1]\n",
      "    show_points(labels[0].cluster)\n",
      "    print('@@')\n",
      "    show_points(labels[1].cluster)\n",
      "    print('@@')\n",
      "    minsseDict = {}\n",
      "    clusterDict = {}\n",
      "    # \u5047\u8a2d\u57f7\u884cnum_basic_kmeans\u6b21 \u6240\u9700\u57f7\u884ck-1\u6b21bisecting_Kmeans \u7b2c\u4e00\u6b21\u4ee5\u57f7\u884c\uff0c\u6545\u5269\u4e0bk-1-1 = k-2\u6b21\n",
      "    for nbk in range(nbk-2):\n",
      "        sse0 = costfunction(labels,labels[0].cluster)\n",
      "        minsseDict[nbk]=sse0\n",
      "        clusterDict[nbk]=labels[0].cluster\n",
      "        # \u4e00\u6b21\u5206\u5169cluster \u6545+2\u907f\u514d\u91cd\u8986\n",
      "        sse1 = costfunction(labels,labels[1].cluster)\n",
      "        minsseDict[nbk+2]=sse1\n",
      "        clusterDict[nbk+2]=labels[1].cluster\n",
      "        # find minsseDict min value\n",
      "        key = max(minsseDict.iteritems(), key=operator.itemgetter(1))[0]\n",
      "        tppoints = clusterDict[key]\n",
      "        del minsseDict[key]\n",
      "        del clusterDict[key]\n",
      "        sse,labels = basic_kmeans(2,tppoints,nbk*2+2,times)\n",
      "        # \u6bcf\u4e00\u6b21\u53bb\u5206\u985e\u7684points\n",
      "        print('@@')\n",
      "        show_points(tppoints)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# \u4ee5 first sse = sum of square error \u4f86\u627e\u51fa\u8f03\u597d\u7684\u521d\u59cb\u9ede\n",
      "def optimization(k,points,times):\n",
      "    if times != 0:\n",
      "        sseList=[]\n",
      "        labelList=[]\n",
      "        for a in range(times):\n",
      "            labels = initialization_label(k,points)\n",
      "            sse = costfunction(labels,points)\n",
      "            sseList.append(sse)\n",
      "            labelList.append(labels)\n",
      "            best_labels = labelList[sseList.index(min(sseList))]\n",
      "    else:\n",
      "        best_labels = initialization_label(k,points)\n",
      "    return best_labels"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def choose_k(points,k_range,times):\n",
      "    k_candidate=[]\n",
      "    # \u5e36\u5165k\u7684\u7bc4\u570d\n",
      "    for k in range(1,k_range):\n",
      "        best_labels = optimization(k,points,times)\n",
      "        sse,labelList = basic_kmeans(k,points,0,times)\n",
      "        k_candidate.append(sse)\n",
      "    sse_slopeList=[0,0]\n",
      "    print(k_candidate)\n",
      "    for a in range(len(k_candidate)-1):\n",
      "        # \u7b97\u51fa\u4e0d\u540ck\u503c\u7684\u659c\u7387 \u6839\u64daelbow \u6c42\u51fa best_k\n",
      "        sse_slope = k_candidate[a+1]-k_candidate[a]\n",
      "        sse_slopeList.append(sse_slope)\n",
      "    #\u9078\u51fa\u6700\u659c\u7387\u8b8a\u5316\u6700\u5927    \n",
      "    best_k = sse_slopeList.index(min(sse_slopeList))\n",
      "    return best_k"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# basic_kmeans\n",
      "basic_kmeans(4,points,0,10)\n",
      "show_points(points)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0:\u5206\u985e0\tfeature-0:0.1\t1:0.1\t\n",
        "1:\u5206\u985e0\tfeature-0:0.1\t1:0.2\t\n",
        "2:\u5206\u985e0\tfeature-0:0.2\t1:0.1\t\n",
        "3:\u5206\u985e0\tfeature-0:0.2\t1:0.2\t\n",
        "4:\u5206\u985e1\tfeature-0:10.1\t1:0.1\t\n",
        "5:\u5206\u985e1\tfeature-0:10.1\t1:0.2\t\n",
        "6:\u5206\u985e1\tfeature-0:10.2\t1:0.2\t\n",
        "7:\u5206\u985e1\tfeature-0:10.2\t1:0.1\t\n",
        "8:\u5206\u985e2\tfeature-0:0.1\t1:10.1\t\n",
        "9:\u5206\u985e2\tfeature-0:0.2\t1:10.1\t\n",
        "10:\u5206\u985e2\tfeature-0:0.1\t1:10.2\t\n",
        "11:\u5206\u985e2\tfeature-0:0.2\t1:10.2\t\n",
        "12:\u5206\u985e3\tfeature-0:10.1\t1:10.1\t\n",
        "13:\u5206\u985e3\tfeature-0:10.1\t1:10.2\t\n",
        "14:\u5206\u985e3\tfeature-0:10.2\t1:10.2\t\n",
        "15:\u5206\u985e3\tfeature-0:10.2\t1:10.1\t\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# depend on elbow theorem find bestk\n",
      "choose_k(points,6,10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[800.0799999999999, 400.0799999999999, 200.07999999999993, 0.07999999999999972, 0.06999999999999972]\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# bisecting_Kmeans\n",
      "bisecting_Kmeans(points,4,10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0:\u5206\u985e0\tfeature-0:10.1\t1:0.1\t\n",
        "1:\u5206\u985e0\tfeature-0:10.1\t1:0.2\t\n",
        "2:\u5206\u985e0\tfeature-0:10.2\t1:0.2\t\n",
        "3:\u5206\u985e0\tfeature-0:10.2\t1:0.1\t\n",
        "4:\u5206\u985e0\tfeature-0:10.1\t1:10.1\t\n",
        "5:\u5206\u985e0\tfeature-0:10.1\t1:10.2\t\n",
        "6:\u5206\u985e0\tfeature-0:10.2\t1:10.2\t\n",
        "7:\u5206\u985e0\tfeature-0:10.2\t1:10.1\t\n",
        "@@\n",
        "0:\u5206\u985e1\tfeature-0:0.1\t1:0.1\t\n",
        "1:\u5206\u985e1\tfeature-0:0.1\t1:0.2\t\n",
        "2:\u5206\u985e1\tfeature-0:0.2\t1:0.1\t\n",
        "3:\u5206\u985e1\tfeature-0:0.2\t1:0.2\t\n",
        "4:\u5206\u985e1\tfeature-0:0.1\t1:10.1\t\n",
        "5:\u5206\u985e1\tfeature-0:0.2\t1:10.1\t\n",
        "6:\u5206\u985e1\tfeature-0:0.1\t1:10.2\t\n",
        "7:\u5206\u985e1\tfeature-0:0.2\t1:10.2\t\n",
        "@@\n",
        "@@\n",
        "0:\u5206\u985e2\tfeature-0:10.1\t1:0.1\t\n",
        "1:\u5206\u985e2\tfeature-0:10.1\t1:0.2\t\n",
        "2:\u5206\u985e2\tfeature-0:10.2\t1:0.2\t\n",
        "3:\u5206\u985e2\tfeature-0:10.2\t1:0.1\t\n",
        "4:\u5206\u985e3\tfeature-0:10.1\t1:10.1\t\n",
        "5:\u5206\u985e3\tfeature-0:10.1\t1:10.2\t\n",
        "6:\u5206\u985e3\tfeature-0:10.2\t1:10.2\t\n",
        "7:\u5206\u985e3\tfeature-0:10.2\t1:10.1\t\n",
        "@@\n",
        "0:\u5206\u985e4\tfeature-0:0.1\t1:0.1\t\n",
        "1:\u5206\u985e4\tfeature-0:0.1\t1:0.2\t\n",
        "2:\u5206\u985e4\tfeature-0:0.2\t1:0.1\t\n",
        "3:\u5206\u985e4\tfeature-0:0.2\t1:0.2\t\n",
        "4:\u5206\u985e5\tfeature-0:0.1\t1:10.1\t\n",
        "5:\u5206\u985e5\tfeature-0:0.2\t1:10.1\t\n",
        "6:\u5206\u985e5\tfeature-0:0.1\t1:10.2\t\n",
        "7:\u5206\u985e5\tfeature-0:0.2\t1:10.2\t\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show_points(points)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0:\u5206\u985e4\tfeature-0:0.1\t1:0.1\t\n",
        "1:\u5206\u985e4\tfeature-0:0.1\t1:0.2\t\n",
        "2:\u5206\u985e4\tfeature-0:0.2\t1:0.1\t\n",
        "3:\u5206\u985e4\tfeature-0:0.2\t1:0.2\t\n",
        "4:\u5206\u985e2\tfeature-0:10.1\t1:0.1\t\n",
        "5:\u5206\u985e2\tfeature-0:10.1\t1:0.2\t\n",
        "6:\u5206\u985e2\tfeature-0:10.2\t1:0.2\t\n",
        "7:\u5206\u985e2\tfeature-0:10.2\t1:0.1\t\n",
        "8:\u5206\u985e5\tfeature-0:0.1\t1:10.1\t\n",
        "9:\u5206\u985e5\tfeature-0:0.2\t1:10.1\t\n",
        "10:\u5206\u985e5\tfeature-0:0.1\t1:10.2\t\n",
        "11:\u5206\u985e5\tfeature-0:0.2\t1:10.2\t\n",
        "12:\u5206\u985e3\tfeature-0:10.1\t1:10.1\t\n",
        "13:\u5206\u985e3\tfeature-0:10.1\t1:10.2\t\n",
        "14:\u5206\u985e3\tfeature-0:10.2\t1:10.2\t\n",
        "15:\u5206\u985e3\tfeature-0:10.2\t1:10.1\t\n"
       ]
      }
     ],
     "prompt_number": 24
    }
   ],
   "metadata": {}
  }
 ]
}